package daythree;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/*
 * 来个堆相关的题目  ：  
 * 已知一个 几乎有序的  数组 。几乎 有序 是指 如果 把数组 排好序的 话  数组 中每个 数 移动的距离 不会超过  给定的数 k
 * 请选择 一个合适的 排序策略   
 * 
 * 
 * 
 * 1.自己 手写 一个堆  heap 
 * 系统中   的堆结构  就是  优先级 队列  priorityQueue 底层 就是一个堆  默认是  小根堆 
 * 不过这个堆  以后 在使用 的  时候  可能 不是那么方便 需要  我们 去 改写堆
 * 重要的两个 操作  就是  heapInsert  和  heapify
 * 
 * 
 * 
 * 还有  就是堆的改写 问题
 * 
 * 
 * 2. 比较器
 * 比较器的 实质 ：重载 运算符
 */
public class heapAndComparator {
	// 实验用 的  非 基础类型 
	static class Node {
		String name;
		int age;
		Node next;
		public Node() {
			
		}
		public Node(String name,int age) {
			this.name=name;
			this.age=age;
		}
		public String toString() {
			return "name: "+ name+" age: "+ age;
		}
		
	}
//  这里 还有一个 细节 在这里  再Comparator 没写 泛型的 时候 出现的一个问题
//  注意 这里  是没有  对字符串  进行 compare的    字符串 比较的话 需要 用String  中自带的 compareTo方法	
	static class MyComparator implements Comparator<Node>{
		// 不能 加  static 的问题 就是Java  基础中的抽象类的  知识了
			public int compare(Node o1,Node o2) {
				return o1.age-o2.age;
			}
//
//			@Override
//			public int compare(Object o1, Object o2) {
//				// TODO Auto-generated method stub
//				return 0;
//			}
	
		
	}

	public static void main(String []args) {
/*		//方法一  :
		PriorityQueue<Integer> q=new PriorityQueue<>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return o1-o2;
			}
			
		});
		//方法二: 匿名内部类:实质: 继承该类  或者 实现 该接口的     ** 子类  匿名对象 **  明白   
		//  注意 这两种格式  
		PriorityQueue<Node> qplus=new PriorityQueue<>(new MyComparator());
		
		*/
		// 测出 compareTo的使用  效果吧
		System.out.println("String".compareTo("Strinf"));
		MyComparator com=new MyComparator();
		//  动手操作 真的 明白 了 很多东西 
		MyHeap<Node> heap=new MyHeap<>(com);
		MyHeap<Node> heap1=new MyHeap<>(new Comparator<Node>() {

			@Override
			public int compare(Node o1, Node o2) {
				
				return o1.age-o2.age;
			}
			
		});
		Node n1=new Node("1",24);
		Node n2=new Node("lisi",30);
		Node n3=new Node("zhangsan",13);
		Node n4=new Node("wangwu",30);
		Node n5=new Node("hanjunhao",36);
		Node n6=new Node("zhangqingru",27);
		heap.push(n1);
		heap.push(n2);
		heap.push(n5);
		heap.push(n6);
		heap.push(n3);
		heap.push(n4);
		n1.age=10;
		heap.change(n1);
		System.out.println(heap.pop());
		System.out.println(heap.pop());
		System.out.println(heap.pop());
		System.out.println(heap.pop());
		System.out.println(heap.pop());
		// 测试的 好像是 没毛病的
		
		
	}

}
class MyHeap <V> {
	//  不能声明 泛型类型的数组
	ArrayList<V> heap;
//再声明一个 哈希表 记住 堆中每个 数据的 索引  这个时候的堆已经不是 只能存储 基础类型的堆了
// 引用数据类型 中 成员变量的 改变 这个表 就是针对这种情况的 
	HashMap<V,Integer> indexMap;
	private int heapSize;
// 还得 声明 一个比较器呢  就是一个 接口 这里用的 还是多态的知识
	// 还是第一次 声明 这样的带 泛型的接口 呢
	Comparator <?super V> com;
	///  看到这个  构造器 是不是 明白 很多东西
	public MyHeap(Comparator<? super V > com) {
		heap=new ArrayList<>();
		heapSize=0;
		indexMap=new HashMap<>();
		this.com=com;
	}
	public boolean isEmpty() {
		return heapSize==0;
		
	}
	public boolean containsK(V value) {
		return indexMap.containsKey(value);
	}
	public void change(V value) {
		int valueIndex=indexMap.get(value);
		//  这个值 发生了 变化  只有两种情况 要么 heapInsert  要么 heapify 都写呗 只执行一个
		heapInsert(valueIndex);
		heapify(valueIndex,heapSize);
	}
	public void push(V value) {
		if(containsK(value))
			///        
			return;
		heap.add(value);
		// 要始终 保证 这两个 容器中的 数据 是完全同步的  这就是 同步表 便于操作
		indexMap.put(value, heapSize);
		heapInsert(heapSize++);
	}
	public V pop() {
		V ans = heap.get(0);
//	 应给没有问题吧   我感觉 好像是 没有问题 
//		int end=heapSize-1;
		swap(0,--heapSize);
		heap.remove(heapSize);
		indexMap.remove(ans);
		heapify(0,heapSize);
		return ans;
		
	}
	public void heapify(int index,int heapsize) {
		int left=index*2+1;
		while(left<heapSize) {
			int smallIndex=left+1 < heapSize && (com.compare(heap.get(left), heap.get(left+1)))
					>0 ? left+1: left;
			if(com.compare(heap.get(smallIndex),heap.get(index))<0) {
				swap(smallIndex,index);
				//  这行代码 至关重要   此时 我感觉 那里面的代码  没有一句 废话
				index=smallIndex;
				left=smallIndex*2+1;
			}
			else
				break;
			
		}
		
	}
	public void heapInsert(int index) {
		// 引用数据类型怎么  比较 请让比较器告诉我好嘛  
		while(com.compare(heap.get(index), heap.get((index-1)/2))<0) {
			swap(index,(index-1)/2);
			index=(index-1)/2;
		}
	}
	// 非静态 方法 可以直接 使用 成员变量啊 就不用加什么 容器参数了
	// 不同寻常的交换 方法
	public void swap(int i,int j){
		V o1=heap.get(i);
		V o2=heap.get(j);
		heap.set(i, o2);
		heap.set(j, o1);
		indexMap.put(o1,j);
		indexMap.put(o2,i);
	}

//  z直接 没有isFull  这个函数 	
//	public boolean isFull() {
//		return 
//	}
}
/*/  就是重写一个 普通的堆  只能放入 整型  后面 再改写 有泛型 的堆 以及 复杂的堆
class MyHeap{
	private int arr[];
	private int count;
	private int size;
	public MyHeap() {
		
	}
	public MyHeap(int size) {
		this.size=size;
		arr=new int[size];
		count=0;
	}
	public  boolean isFull() {
		return count==size;
	}
	public  boolean isEmpty() {
		return  count==0;
	}
	public  void push(int value) {
		if(isFull()) {
			System.out.println();
			return ;
		}
		//arr[count++]=value;
	}
	public  void heapInsert(int arr[],int index) {
		while(arr[index]<arr[(index-1)/2]) {
			swap(arr,index,(index-1)/2);
			index=(index-1)/2;
		}
	}
	// 作用当堆中 某个位置上的值 发生变化的时候 是变化之后的堆 仍然 调节成大根堆
	// heapify 是可能向上 调整 也可能向下 调整 由于你变化的这个值决定 调整  而 heapInsert  是向上  调整
	public void  heapify(int arr[],int index) {
		if(arr[index]<=arr[(index-1)/2]) {
			heapInsert(arr,index);
			return ;
		}
		
	}
	public void swap(int arr[],int i, int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
}*/
